#include <iostream>
#include <vector>

using namespace std;
// 98. 验证二叉搜索树
// 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
// https://leetcode.cn/problems/validate-binary-search-tree/
// 思路2：Recursion

/// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
// 递归测试
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return isValidBST(root, INT_MIN, INT_MAX);
    }

private:
    // 判断当前根节点的值 和 左子树的最大值max、右子树的最小值min，之间的关系
   bool isValidBST(TreeNode* node, int min, int max) {
        if(node == NULL)
            return true;
        // 结点的值必须在min和max之间
        if(min != INT_MIN && node->val <= min)   // 不判断等于的时候，因为有重复元素。
            return false;
        if(max != INT_MAX && node->val >= max)
            return false;
        // 检查左子树，更新上界为node->val；检查右子树，更新下界为node->val
        return isValidBST(node->left, min, node->val) && isValidBST(node->right, node->val, max);
    }
};
int main() {
    TreeNode* bst1 = new TreeNode(2, new TreeNode(1), new TreeNode(3));
    cout<<"bst1=" << Solution().isValidBST(bst1) << endl;   // true

    TreeNode* bst2 = new TreeNode(5, new TreeNode(1),
                                  new TreeNode(4, new TreeNode(3), new TreeNode(6))
                                  );
    cout<<"bst2=" << Solution().isValidBST(bst2) << endl;   // false

    TreeNode* bst3 = new TreeNode(2, new TreeNode(2), new TreeNode(2));
    cout<<"bst3=" << Solution().isValidBST(bst3) << endl;   // false

    TreeNode* bst4 = new TreeNode(2, new TreeNode(2, new TreeNode(2), NULL), NULL);
    cout<<"bst4=" << Solution().isValidBST(bst4) << endl;   // false
    return 0;
}
